package com.jzoffer;

/*
* HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:
* 在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。
* 但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},
* 连续子向量的最大和为8(从第0个开始,到第3个为止)。
* 给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
* */
public class TheLargestSumArray {
    public static void main(String[] args) {
        int[] array = {0,-3,-4,-3,-2,0,-3};
        int res = FindGreatestSumOfSubArray(array);
        int res2 =FindGreatestSumOfSubArray2(array);
        System.out.println(res);
        System.out.println(res2);
    }
    public static int FindGreatestSumOfSubArray(int[] array){
        if(array == null || array.length < 1){
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int cur = 0;
        for (int i = 0;i < array.length;i++){
            // 当之前的值累加值<=0 或者全是负数和0情况下 保存累加值和最大值的最大值
            // case 1 以前累加的值<+0 那么加上下一个值的话没有更大的意义 故舍弃
            // case 2 数组全为负数或0 那么保存这些值的最大值（单个值之间的比较）
            if(cur <= 0){
                cur = array[i];
                if(max < cur){
                    max = cur;
                }
            }else{
                // 累加之前的值 >0 那么继续累加 和最大值之间比较 更新最大值
                cur += array[i];
                if(max < cur){
                    max = cur;
                }
            }
        }
        return max;

    }

    // 使用动态规划方法
    public static int FindGreatestSumOfSubArray2(int[] array){
        if(array == null || array.length < 1){
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int cur = 0;
        for (int i = 0;i < array.length;i++){
            // 如果连续的累加值还不如当前的值大，那不如舍弃掉前面的值，当然之前的最大值保存在max中
            cur = Math.max(array[i]  + cur,array[i]);
            max = Math.max(cur,max);
        }
        return max;

    }


}
